import java.util.*;

public class Solution721 {

    private class UnionUtil{
        HashMap<Integer,Integer> Util;
        int Count;
        UnionUtil(){
            Util=new HashMap<>();
            Count=0;
        }
        int getCount(){
            return Count;
        }
        int find(int element){
            if(Util.containsKey(element)==false){
                Util.put(element,element);
                Count++;
            }
            if(Util.get(element)!=element){
                Util.put(element,find(Util.get(element)));
            }
            return Util.get(element);
        }
        boolean union(int x,int y){
            int rootx=find(x);
            int rooty=find(y);
            if(rootx==rooty){
                return false;
            }
            Util.put(rootx,rooty);
            Count--;
            return true;
        }
    }
    
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        ArrayList<ArrayList<String>> newAcc=new ArrayList<>();
        for (List<String> tmpRow:accounts) {
            ArrayList<String> newRow=new ArrayList<>();
            for (String tmpStr:tmpRow) {
                newRow.add(tmpStr);
            }
            newAcc.add(newRow);
        }


        HashMap<String ,Integer> store=new HashMap<>();
        UnionUtil util=new UnionUtil();
        for (int i = 0; i < newAcc.size(); i++) {
            util.find(i);
        }
        
        for (int i = 0; i < newAcc.size(); i++) {
            for (int j=1;j<newAcc.get(i).size();j++) {
                String tmp=newAcc.get(i).get(j);
                if(store.containsKey(tmp)==false){
                    store.put(tmp,i);
                }
                else{
                    util.union(i,store.get(tmp));
                }
            }
        }


        List<List<String>> result=new ArrayList<>();
        for (int i = 0; i < newAcc.size(); i++) {
            int tmpPre=util.find(i);
            if(tmpPre!=i){
                for (int j = 1; j < newAcc.get(i).size(); j++) {
                    newAcc.get(tmpPre).add(newAcc.get(i).get(j));
                }
                newAcc.get(i).clear();
            }
        }


        for (List<String> tmp:newAcc) {
            if(tmp.isEmpty()==false) {
                tmp=new ArrayList<String>(new HashSet<String>(tmp));
                Collections.sort(tmp);
                result.add(tmp);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Solution721 s=new Solution721();
        List list = Arrays.asList("John","johnsmith@mail.com","john_newyork@mail.com");
        List list1 = Arrays.asList("John","johnsmith@mail.com","john00@mail.com");
        List list2 = Arrays.asList("Mary","mary@mail.com");
        List list3 = Arrays.asList("John","johnnybravo@mail.com");
        List<List<String>> all=new ArrayList<>();
        all.add(list);
        all.add(list1);
        all.add(list2);
        all.add(list3);
        System.out.println(s.accountsMerge(all));
    }
}
